package t_993

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func isCousins(root *TreeNode, x int, y int) bool {
	type DNode struct {
		depth int
		node  *TreeNode
	}
	var xDepth, yDepth int
	var xNode, yNode *TreeNode

	q := []DNode{}
	q = append(q, DNode{0, root})
	for len(q) > 0 {
		dnode := q[0]
		q = q[1:]
		node, depth := dnode.node, dnode.depth
		if (node.Left != nil && node.Left.Val == x) || (node.Right != nil && node.Right.Val == x) {
			xNode = node
			xDepth = depth + 1
		}
		if (node.Left != nil && node.Left.Val == y) || (node.Right != nil && node.Right.Val == y) {
			yNode = node
			yDepth = depth + 1
		}
		if node.Left != nil {
			q = append(q, DNode{depth + 1, node.Left})
		}
		if node.Right != nil {
			q = append(q, DNode{depth + 1, node.Right})
		}
	}
	return xDepth == yDepth && xNode != yNode
}
